/*  slfcombl.cpp  by K.Tsuru  */
// function ID 4100 DRADIX
/*************************************************
SLong class
It provides a binomial coefficient(combination number) nCk.
n < k : error
**************************************************/
#ifndef SN_H
#include "sn.h"
#endif

/***********************************************************************
It provides a main body for binomial coefficient calculated by a formula
         n    n-1   n-2   n-3         n-k+1
  nCk = --- x --- x --- x --- x ... x -----
         1     2     3     4            k
It is used the fact that any partial product is an integer.
*************************************************************************/
SLong combL(ulong n, ulong k){
    if( n < k ) SNManager::SetError(SNManager::DOMAIN_ERR,"combL()", 4100);
    if( n - k < k ) k = n - k;
    if( k <= 1u ) return k ?  n : 1;
#if 1
    SInteger nCk(n);
    ulong mt = nCk.SlOpMaxValue(); // =131071
//It uses SInteger IsMult() and IsDiv().
    if(n < mt){ // k < n < mt
        ulong j;
        for(j = 1; j < k ; j++){
            IsMult(nCk, n - j, nCk);
            IsDiv(nCk, j + 1, nCk);
        }
        return nCk.ConvToDec(); //radix conversion
    } else { // uses SLong
        SLong  r(n);
        ulong j;
        for(j = 1; j < k ; j++){ r= LsMult(r,n - j);    r = LsDiv(r, j + 1); }

        return r;
    }
#else
// SLong version
        SLong  r(n);
        ulong j;
        for(j = 1; j < k ; j++){ r= LsMult(r,n - j);    r = LsDiv(r, j + 1); }

        return r;
#endif
}